There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VoIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers.
This has led to the development of massively parallel, distributed architecture routers. A distributed architecture router typically comprises a large number of routing nodes that are coupled to each other via a plurality of switch fabric modules and an optional crossbar switch. Each routing node has its own routing (or forwarding) table for forwarding data packets via other routing nodes to a destination address.
Current generation high-speed routers do not provide much in the way of traffic profiling capability. Traffic profiling is performed by external test equipment instead. However, using external test equipment to profile data traffic is costly, since the test equipment must be purchased in addition to the router. This equipment is very expensive if high bandwidth links are analyzed.
Similarly, most billing functions are relegated to access points. Conventional routers do not provide billing information on traffic flowing through the router, but rather provide billing information for terminating traffic only. There is no way of charging for peak data flow at busy times in intermediate routers to encourage movement of massive amounts of data to slack periods and to spread network load more evenly over time. This kind of control is left to the terminating points, such as access points. Thus, intermediate routers, including core routers, depend upon access points to control their traffic.
The Applicants filed U.S. patent application Ser. No. 10/841,128, entitled “Apparatus and Method for Packet Length and Enhanced Traffic Profiling in a Massively Parallel Router” on May 7, 2004. Application Ser. No. 10/841,128 was directed to a high-speed router comprising a plurality of routing nodes coupled to a switch fabric. Each routing node determines packet lengths of data packets received in the routing node and sums packet lengths of data packets associated with particular routes. Each routing node comprises route counters that store counts of data packets for particular routes and store packet length sum values of data packets for particular routes. The routing node calculates a first bandwidth value from a first data packet count and a first packet length sum value stored in the route counters.
The Applicants also filed U.S. patent application Ser. No. 10/840,988, entitled “Apparatus and Method for Traffic Profiling in a Massively Parallel Router” on May 7, 2004. Application Ser. No. 10/840,988 was directed to a high-speed router comprising a plurality of routing nodes coupled to a switch fabric. Each routing node identifies at least one traffic type indicia associated with data packets and counts data packets based on traffic type indicia. Each routing node stores route counters and identification (ID) counters. The route counters store data packet counts for particular routes. The ID counters store data packet counts for particular traffic type indicia.
The subject matter disclosed in U.S. patent application Ser. Nos. 10/841,128 and 10/840,988 is hereby incorporated by reference in the present disclosure as if fully set forth herein. The routers disclosed in patent application Ser. Nos. 10/841,128 and 10/840,988 make extensive use of packet counters and packet length adders that track the number and type of data packets associated with each route, thereby enabling traffic profiling to be performed.
Normally, packet counter or summation updates in a multi-processor environment are done through atomic read-modify-write instructions or through coordination among the multiple processors in such a system. In some prior art multiprocessor systems, this coordination may be done using time slices for each processor to gain access or through a software semaphore. However, the microengines of some data processors may not implement atomic read-modify-write instructions. Also, in some embodiments, the use of time slices may be impractical, since packet processing may be performed simultaneously by many microengines and threads and any form of synchronization would slow down the forwarding threads. Furthermore, software semaphores may increase the workload by requiring accesses to the semaphore and wait states for other threads to finish their access.
Therefore, there is a need in the art for improved high-speed routers capable of profiling data traffic through the router. In particular, there is a need for improved packet counters and packet adders that may be accessed and incremented by multiple processors and/or microengines without using read-modify-write instructions and without using synchronized time slices or software semaphores.